import javax.swing.text.AbstractDocument;

public class BinaryTree {

    static class TreeNode {
        public char val;  //数据域
        public TreeNode left;  //左孩子引用，常常代表左孩子为根的整颗左子树
        public TreeNode right; //右孩子引用，常常代表右孩子为根的整颗右子树

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        //E.right = H;
        return A;
    }

    //前序遍历 根结点-> 根的左子树 -> 根的右子树
    public void preOrder(TreeNode root) {
        if (root == null) return;
        System.out.println(root.val + " ");  //根
        preOrder(root.left);  //左
        preOrder(root.right);  //右
    }

    //中序遍历 左子树-> 根结点 -> 右子树
    public void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);  //左
        System.out.println(root.val + " "); //根
        inOrder(root.right);  //右
    }

    //后序遍历 左子树-> 右子树 -> 根结点
    public void postOrder(TreeNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.val + " ");
    }

    public int nodeSize;

    //获取树中结点个数  - 遍历思路
    public void getNodeSize(TreeNode root) {
        if (root == null) return;
        nodeSize++;
        getNodeSize(root.left);
        getNodeSize(root.right);
    }

    //子问题
    public int getNodeSize2(TreeNode root) {
        //如果根结点不为空，返回自身加上左子树的结点个数和右子树的结点个数之和
        if (root == null)
            return 0;
        return getNodeSize2(root.left) + getNodeSize2(root.right) + 1;
    }


    //获取叶子结点的个数 - 遍历思路
    public int leafCount;

    public void getLeafNodeCount(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            leafCount++;
        }
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.left);
    }

    //子问题
    public int getLeafNodeCount2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right) + 1;
    }


    //求第K层的结点个数
    public int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        if (k == 1) {
            return 1; //当K为1时，说明只有根结点这一层，因此直接返回1即可(1个结点)
        }
        //此时K不为1，就继续寻找下一层
        return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
    }


    //求树的高度
    public int getHight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = getHight(root.left);
        int rightHight = getHight(root.right);
        //树的高度 = 当前层 + 子树的高度
        return Math.max(leftHeight, rightHight) + 1;
    }


    //检测值为value的元素是否存在
    public TreeNode find(TreeNode root, char key) {
        if (root == null) {
            return null;
        }
        if (root.val == key) {
            return root;
        }
        TreeNode leftResult = find(root.left, key);
        if (leftResult != null) {
            return leftResult;
        }
        TreeNode rightResult = find(root.right, key);
        if (rightResult != null) {
            return rightResult;
        }
        return null;
    }

}
